package com.zhugang.september;

/**
 * @program algorithms
 * @description: test
 * @author: chanzhugang
 * @create: 2021/09/20 23:35
 */
public class HoldWater {

    /**
     * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     */
    public static void main(String[] args) {
        int[] arr = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        int max = holeWater2(arr);
        System.out.println(max);
    }

    /**
     * 盛水最多：枚举， 这种居然在leetcode通不过，超时
     */
    public static int holdWater(int[] arr) {
        int max = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int area = (j - i) * Math.min(arr[i], arr[j]);
                max = Math.max(max, area);
            }
        }
        return max;
    }

    /**
     * 双指针，左右偏移:高度取最小值
     */
    public static int holeWater2(int[] arr) {
        int max = 0;
        for (int i = 0, j = arr.length - 1; i < j; ) {
            int minHeight = arr[i] < arr[j] ? arr[i++] : arr[j--];
            max = Math.max(max, (j - i + 1) * minHeight);
        }
        return max;
    }
}